The present invention relates to the fields of computer performance analysis and data converter testing, and more particularly to the field of methods and apparatuses for counting the occurrence of different data patterns as they appear on a communication bus within a computer system or on the output of an analog to digital converter.
In analyzing the performance of a computer system as it executes a program, or in analyzing the performance of an analog to digital converter, it is frequently desirable to be able to count the occurrence of each of a variety of different digital patterns as they appear on a bus or the output of the converter. In many cases, the desired count should reflect the duration of the patterns of data, as well as its initial occurrence. When a variety of such data patterns are occurring rapidly, and there is a need to identify them and count the occurrences of each particular pattern, an apparatus is needed which can sort and count such patterns as rapidly as possible with a minimum of hardware.
Prior art solutions to this problem have included a variety of methods. A straightforward approach, but one which is hardware intensive, is to dedicate a word recognizer and a counter to the tasks of recognizing each pattern and counting the data valid signals that occur while that pattern is present. For a large number of such patterns, this approach is prohibitively expensive, since significantly more circuitry is required for each additional pattern of interest.
An improvement on this scheme is to use only one counter to do all of the counting, but keep track of separate sums for each different pattern of interest. Such a technique is described in a paper by Steven Kerman, entitled: A Facility for Analyzing Microprocessor System Performance, published in the Digest of Papers, IEEE Compcon, 1979. In this system, a large number of counters are simulated by one counter and a random access memory. During the occurrence of each event the counter counts clock pulses and its concluding count is added to a stored value in memory. The same adder is successively employed to update many different memory locations. While this approach is more effective than a multiplicity of counters, it is still somewhat hardware intensive and slower than desired because of the time required for operation of the adder. A lack of speed can significantly limit the usefulness of a data occurrence frequency analyzer in real-time applications.
A further improvement to this technology is disclosed in U.S. Pat. No. 4,774,681 to Arnold Frish for a "Method and Apparatus for Providing a Histogram", Sept. 27, 1988. Frish improved on the method of Kerman by eliminating the adder and substituting a linear feedback shift register for the conventional counter. By eliminating the adder, significant time savings are made possible, increasing the maximum speed of operation attainable. Similarly, the substitution of the linear feedback shift register for the conventional counter also produces some time savings.
Nonetheless, there is still room for improvement over the method disclosed by Frish. In Frish's approach, it takes time to load and unload the shift register, creating a limitation on the maximum speed that is attainable with any particular implementation technology. What is desired is an even faster and more efficient method of counting the number of times that each of a large number of different digital patterns are present.